package com.leet;

import java.util.Arrays;

public class NQueenTo {
    private int ans;
    char[][] initBoard(char[][] board){
        for(char[] chars:board){
            Arrays.fill(chars,'.');
        }
        return board;
    }
    Boolean isValid(char[][] board,int n,int row,int col){
        for(int i = 0;i < row; i++){
            if(board[i][col]=='Q'){
                return false;
            }
        }
        for(int i = row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(board[i][j]=='Q'){
                return false;
            }
        }
        for(int i = row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(board[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
    public void backTracking(char[][] board,int n,int row){
        if(n==row){
            ans += 1;
            return;
        }
        for(int i = 0;i < n;i++){
            if(isValid(board,n,row,i)){
                board[row][i] = 'Q';
                backTracking(board,row+1,i);
                board[row][i] = '.';
            }
        }
    }
    public int totalNQueens(int n) {
        ans = 0;
        char[][] board = new char[n][n];
        board = initBoard(board);
        backTracking(board,n,0);
        return ans;
    }
}
